package com.celan.year2022.day1223;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    public int openLock(String[] deadends, String target) {
        if ("0000".equals(target)) {
            return 0;
        }
        HashSet<String> visited = new HashSet<>();
        Queue<String> que = new LinkedList<>();
        que.add("0000");
        for (String deadend : deadends) {
            visited.add(deadend);
        }
        if (visited.contains("0000")) return -1;
        visited.add("0000");

        int count = 0;
        while (!que.isEmpty()) {
            int size = que.size();
            for (int i = 0; i < size; i++) {
                String poll = que.poll();
                if (poll.equals(target)) {
                    return count;
                }

                for (int j = 0; j < 4; j++) {
                    String plus = plus(poll, j);
                    if (!visited.contains(plus)) {
                        que.add(plus);
                        visited.add(plus);
                    }
                    String min = min(poll, j);
                    if (!visited.contains(min)) {
                        que.add(min);
                        visited.add(min);
                    }
                }
            }
            count++;
        }
        return -1;
    }

    String plus(String s, int n) {
        char[] chars = s.toCharArray();

        if (chars[n] == '9') {
            chars[n] = '0';
        } else {
            chars[n]++;
        }
        return new String(chars);
    }

    String min(String s, int n) {
        char[] chars = s.toCharArray();

        if (chars[n] == '0') {
            chars[n] = '9';
        } else {
            chars[n]--;
        }
        return new String(chars);
    }
}